package algotithm.acwing.sort.test838;

import java.util.Arrays;

/**
 * @author zhouyanxiang
 * @Date 2021-01-2021/1/21-23:55
 */
public class Main {
    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        System.out.println("请输入要排序的数组的长度：");
//        int n = scanner.nextInt();
//        int[] arr = new int[n];
//        System.out.println("请输入要排序的数组：");
//        for (int i = 0; i < n; i++) {
//            arr[i] = scanner.nextInt();
//        }
//        scanner.close();
        int[] arr = {5,4,8,9,6};
        buildHeap(arr);
    }

    public static void buildHeap(int[] arr) {
        int length = arr.length;
        // 先构建一个大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            maximumHeap(arr,i, arr.length);
        }
        // 排序
        for (int i = arr.length - 1; i >= 0; i--) {
            // 过程中的每一步数组元素的变化过程
            System.out.println(Arrays.toString(arr));
            swap(arr,0,i);
            length--;
            maximumHeap(arr,0, length);
        }

        System.out.println(Arrays.toString(arr));
    }

    public static void maximumHeap(int[] arr,int i ,int length) {
        int tmp = arr[i];
        for (int j = 2 * i + 1;j < length; j = j * 2 + 1) {
            // 右孩子比左孩子要大，那么指向右孩子
            if (j+1 < length && arr[j] < arr[j+1]) {
                j++;
            }
            // 右孩子比根节点要大，一直往下探寻
            if (arr[j] > tmp) {
                arr[i] = arr[j];
                i = j;
            }
            //将temp放到最终位置
            arr[i] = tmp;
        }
    }

    public static void swap(int[] arr,int a,int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}
